The present invention relates to a secret key generating method for generating a secret key of an entity, to a common key generating method for generating a common key between entities, to an encryption method for encrypting information so that the contents of the information cannot be seen by a party other than the interested parties, to a cryptographic communication method and cryptographic communication system for carrying out information communication between entities through a ciphertext and to a memory product/data signal embodied in carrier wave for recording/transmitting an operation program for the above secret key generating method.
In the modern society, called a highly information-oriented society, based on a computer network, important business documents and image information are transmitted and communicated in a form of electronic information. Such electronic information can be easily copied, so that it tends to be difficult to discriminate its copy and original from each other, thus bringing about an important issue of data integrity. In particular, it is indispensable for establishment of a highly information oriented society to implement such a computer network that meets the factors of “sharing of computer resources,” “multi-accessing,” and “globalization,” which however includes various factors contradicting the problem of data integrity among the parties concerned. In an attempt to eliminate those contradictions, encrypting technologies which have been mainly used in the past military and diplomatic fields in the human history are attracting world attention as an effective method for that purpose.
A cipher communication is defined as exchanging information in such a manner that no one other than the participants can understand the meaning of the information. In cipher communication, encryption is defined as converting an original text (plaintext) that can be understood by anyone into a text (ciphertext) that cannot be understood by the third party and decryption is defined as restoring a ciphertext into a plaintext, and cryptosystem is defined as the overall processes covering both encryption and decryption. The encryption and decryption processes use secret information called an encryption key and a decryption key, respectively. Since the secret decryption key is necessary in decryption, only those knowing this decryption key can decrypt ciphertexts, thus maintaining data security.
The encryption key and the decryption key may be either the same or different from each other. A cryptosystem using the same key is called a common-key cryptosystem, and DES (Data Encryption Standards) employed by the Standard Agency of the USA Commerce Ministry is a typical example. As an example of the cryptosystem using the keys different from each other, a cryptosystem called a public-key cryptosystem has been proposed. In the public-key cryptosystem, each user (entity) utilizing this cryptosystem generates a pair of encryption and decryption keys and publicizes the encryption key in a public key list, thereby keeping only the decryption key in secret. In this public-key cryptosystem, the paired encryption and decryption keys are different from each other, so that the public-key cryptosystem has a feature that the decryption key cannot be known from the encryption key with a one-way function.
The public-key cryptosystem is a breakthrough in cryptosystem which publicizes the encryption key and meets the above-mentioned three factors required for establishing highly information-oriented society, so that it has been studied actively for its application in the field of information communication technologies, thus leading RSA cryptosystem being proposed as a typical public-key cryptosystem. This RSA cryptosystem has been implemented by utilizing the difficulty of factorization into prime factors as the one-way function. Also, a variety of other public-key cryptosystems have been proposed that utilize the difficulty of solving discrete logarithm problems.
Besides, a cryptosystem has been proposed that utilizes ID (identification) information identifying individuals, such as post address and name of each entity. This cryptosystem generates an encryption/decryption key common to a sender and a recipient based on ID information. Besides, the following ID-information based cryptosystems are provided: (1) a technique which needs a preliminary communication between the sender and the recipient prior to a ciphertext communication and (2) a technique which does not need a preliminary communication between the sender and the recipient prior to a ciphertext communication. The technique (2), in particular, does not need a preliminary communication, so that its entities are very convenient in use, thus considered as a nucleus for the future cryptosystems.
A cryptosystem according to this technique (2) is called ID-NIKS (ID-based non-interactive key sharing scheme), whereby sharing an encryption key without a preliminary communication is enabled by employing ID information of a communication partner. The ID-NIKS needs not exchange a public key or a secret key between a sender and a recipient nor receive a key list or services from third parties, thus securing safe communications between any given entities.
FIG. 1 shows principles for this ID-NIKS system. This system assumes the presence of a reliable center as a key generating agency, around which a common-key generation system is configured. In FIG. 1, the information specific to an entity A, i.e. its ID information of a name, a post address, a telephone number, etc. is represented by h(IDA) using a hash function h(•). For an any given entity A, the center calculates secret information SAi as follows on the basis of center public information {PCi}, center secret information {SCi} and ID information h(IDA) of the entity A, and sends it to the entity A secretly:SAi=Fi({SCi}, {PCi}, h(IDA))
The entity A generates, for communications between itself and another arbitrary entity B, a common key KAB for encryption and decryption with its own secret {SAi}, center public information {PCi} and entity B's ID information h(IDB) of the partner entity B as follows:KAB=f({SAi}, {PCi}, h(IDB))
The entity B also generates a common key KBA for the entity A similarly. If a relationship of KAB=KBA holds true always, these keys KAB and KBA can be used as the encryption and decryption keys between the entities A and B.
In the above-mentioned public-key cryptosystem, for example, an RSA cryptosystem, its public key measures 10-fold and more as long as the presently used telephone number, thus being very troublesome. To guard against this, in-the ID-NIKS, each ID information can be registered in a form of name list to thereby be referenced in generating a common key used between any given entities. Therefore, by safely implementing such an ID-NIKS system as shown in FIG. 1, a convenient cryptosystem can be installed over a computer network to which a lot of entities are subscribed. For these reasons, the ID-NIKS is expected to constitute a core of the future cryptosystem.
This ID-NIKS has the two following problems. One is the point that the center becomes a Big Brother (grasps the secret of all entities so as to become a key escrow system). The other one is the point that there is a possibility of enabling operation of the secret of the center in the case that a certain number of entities collude. As for this collusion problem, though a great number of devices are carried out to avoid this in a calculation amount manner, it is difficult to solve the problem completely.
The difficulty of this collusion problem is due to the fact that a secret parameter based on identification information (ID information) becomes a double structure of a center secret and a individual secret. In ID-NIKS it is necessary to form a cryptosystem of a parameter publicized by the center, identification information (ID information) publicized individually and secret parameters for these two types and, in addition, not to expose the center secret even in the case that an entity shows an individual secret delivered to itself to another. Therefore, the realization of the construction of this cryptosystem has many problems to be solved.
Then the present inventors divide identification information (ID information) into several pieces, propose to deliver all of the secret keys based on the divided identification information (ID information) from, respectively, a plurality of centers to entities so that the mathematical structure can be limited to the minimum, which makes the avoidance of the collusion problem possible and propose an encryption method (hereinafter this is referred to as a prior example) by ID-NIKS, of which the construction of that cryptosystem is easy.
The reason why a variety of cryptosystems based on identification information (ID information) of entities proposed for the purpose of solving the collusion problem end up unsuccessful is because the device for preventing the center secret from being found from the collusion information of the entities is attempted to much to be achieved in a mathematical structure. In the case that the mathematical structure becomes too complicated, the method for proving the security also becomes difficult. Therefore, according to the method proposed in the prior example, identification information (ID information) of entities are divided into several pieces and all of the secret keys for each divided identification information (ID information) are delivered to the entities and, thereby, the mathematical structure can be limited to the minimum.
In the prior example a plurality of reliable centers are provided so that each center, respectively, generates a secret key which doesn't have a mathematical structure corresponding to each divided identification information (ID information) of each entity so as to be sent to each entity. Each entity generates a common key, without carrying out a preliminary communication, among these secret keys sent from the centers and identification information (ID information) of which the communication partner are made public. The components corresponding to the communication partner which are included in each of those secret keys are, respectively, extracted so as to generate a common key by synthesizing and adding the extracted components. Therefore, each center does not become a Big Brother because one center does not grasp the secret of all of the entities.
In the following the summary of this prior example is described. An ID vector which is identification information showing name, address, or the like, of each entity is assumed to be an L dimensional binary vector and the ID vector is divided into J blocks for each block size M. For example, the ID vector of the entity A(vector IA) is divided as in the following (1). Each vector IAj( 1, 2, . . . , J), which is the divided identification information, is called an ID division vector. Here, a public ID vector of each entity is converted into L(=MJ) bits by the hash function. In addition, J centers are provided in accordance with the number of divisions of the ID vector so that center numbers are denoted as j=1, 2, . . . , J.                                           I            X                    →                =                  [                                                    I                X1                            →                        ⁢                          |                        ⁢                                          I                X2                            →                        ⁢                          |                        ⁢                                                  ⁢            ⋯            ⁢                                                  ⁢                          |                        ⁢                                          I                XJ                            →                                ]                                    (        1        )            
The j-th center forms a symmetric matrix Hj(2M×2M) of which elements are random numbers. Here, the size of the common key is assumed to be S so as to achieve the following (2) to (4).                               H          j                =                  (                      k            ab                          (              j              )                                )                                    (        2        )                                          k          ab                      (            j            )                          ∈                  Z                      2            S                                              (        3        )                                a        ,                  b          ∈                      Z                          -                              2                M                                                                        (        4        )            
In addition, the j-th center secretly delivers to each entity a row vector corresponding to its ID division vector from the symmetric matrix Hj. That is to say, the vector SAj=Hj [vector IAj] is delivered to the entity A. This Hj[vector IAj] represents a vector obtained by extracting one row which corresponds to the vector IAj from the symmetric matrix Hj. The parameter delivered to each entity is called a secret vector.
A common key is assumed to be shared between the entities A and B. The entity A extracts the components corresponding to the entity B from each secret vector received from each center and synthesizes these J components so that, thereby, a common key for the entity B is generated. The entity B also generates a common key for the entity A in the same way. According to the symmetry of the secret matrix Hj generated by each center, the entities A and B can share the same common key. The common key generated in this way is used to carry out the encryption process and the decryption process between the entities A and B.
The present inventors have studied the improvement of such a prior example and have attempted to construct a cryptographic communication system to which the prior example is applied. This prior example has the excellent advantage that the common key can be shared at a very high speed. However, though it cannot be taken into consideration that the entire ID vectors agree for each entity, it can be taken into account that an ID division vector that is a part of them becomes identical. Therefore, there is the defect of being weak against a collusion attack where a plurality of entities collude and offer their own secret partial key so as to pretend to be another entity of which the entire ID vector is formed by a synthesis of ID division vectors of the respective entities and, therefore, further improvement is desired. Such a defect is due to the fact that a part of the secret symmetric matrix of each center is delivered to an entity as it is.